package com.cdy.demo.algorithm;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Leetcode322 {

    public static void main(String[] args) {
        Leetcode322 leetcode322 = new Leetcode322();
        System.out.println(leetcode322.coinChange2(new int[]{1, 2, 5}, 11));
        System.out.println(leetcode322.coinChange(new int[]{2}, 3));
        System.out.println(leetcode322.coinChange(new int[]{1}, 0));
        System.out.println(leetcode322.coinChange(new int[]{1}, 1));
        System.out.println(leetcode322.coinChange(new int[]{1}, 2));

    }

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i <amount + 1; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                int index = i - coins[j];
                if (index>=0 && dp[index] < min && dp[index]>=0) {
                    min = dp[index];
                }
            }
            if (min == Integer.MAX_VALUE) {
                dp[i] = -1;
            } else {
                dp[i] = min + 1;
            }
        }
        return dp[amount];
    }

    public int coinChange2(int[] coins, int amount) {
        if (amount ==0) return 0;
        if (coins.length == 0) return -1;

        int len = coins.length;
        int[][] dp = new int[len + 1][amount + 1];

        for (int i = 0; i < len + 1; i++) {
            for (int j = 0; j < amount + 1; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j]=0;
                } else if (i == 0) {
                    dp[i][j] = amount + 1;
                } else if (j == 0) {
                    dp[i][j] = 0;
                } else {
                    if (j >= coins[i - 1]) {
                         // 硬币可重复选， 是重复背包问题， 所以继续是i
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }
        return dp[len][amount] == amount + 1 ? -1 : dp[len][amount];

    }

    /**
     * 518 零钱兑换2
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {

        int len = coins.length;
        int[][] dp = new int[len + 1][amount + 1];

        for (int i = 0; i < len + 1; i++) {
            for (int j = 0; j < amount + 1; j++) {
                if (i == 0 && j == 0) { //要求为0，刚好一次
                    dp[i][j]=1;
                } else if (i == 0) { // 钢镚为0.没法做到
                    dp[i][j] =0;
                } else if (j == 0) { //要求为0.算一次
                    dp[i][j] = 1;
                } else {
                    if (j >= coins[i - 1]) {
                        //不选这个硬币能达到的最大， 或者选了这个硬币， 总数不需要要+1
                        dp[i][j] = dp[i - 1][j] +  dp[i][j - coins[i - 1]] ;
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }
        return dp[len][amount];
    }

    /**
     * 494 目标合
     * @param nums
     * @param S
     * @return
     */

    int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        dfs(nums, S, 0, 0);

        return count;
    }

    private void dfs(int[] nums, int S, int offset, int total) {

        if (offset == nums.length) {
            if (S == total) {
                count++;
            }
            return;
        }
        dfs(nums, S, offset + 1, total + nums[offset]);
        dfs(nums, S, offset + 1, total - nums[offset]);
    }


    class Entry  {
        int offset;
        int total;

        public Entry(int offset, int total) {
            this.offset = offset;
            this.total = total;
        }

        @Override
        public int hashCode() {
            return offset + total;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Entry) {
                return ((Entry) obj).offset == this.offset && ((Entry) obj).total==this.total;
            } else {
                return false;
            }
        }
    }

    HashMap<Entry, Integer> map = new HashMap<>();
    public int findTargetSumWays2(int[] nums, int S) {

        return dfs2(nums, S, 0, 0);
    }

    private int dfs2(int[] nums, int S, int offset, int total) {
        Entry key = new Entry(offset, total);
        if (map.containsKey(key)){
           return map.get(key);
        }
        if (offset == nums.length) {
            if (S == total) {
                return 1;
            }
            return 0;
        }
        int p = dfs2(nums, S, offset + 1, total + nums[offset]);
        int q = dfs2(nums, S, offset + 1, total - nums[offset]);

        map.put(new Entry(offset, total), p + q);
        return p + q;
    }



}
